package com.sourcestruct.linearlist;

/**
 * @author: ZhouBert
 * @date: 2019/6/9
 * @description: 用链表实现循环队列（从表面上看起来比较自然，因为这就是循环链表）
 * 入队在 tail
 * 学习算法的很好的方法就是画图！
 */
public class CircularLinkedQueue<T> {

	private LinkedList<T> head = null;
	/**
	 * 尾的前驱指针
	 */
	private LinkedList<T> tail = null;
	/**
	 * 实际数据大小
	 */
	private int size = 0;

	/**
	 * 入队
	 *
	 * @param obj
	 */
	public void queue(T obj) {
		if (size == 0) {
			head = new LinkedList<>(obj);
			tail = head;
		} else {
			LinkedList<T> node = new LinkedList<>(obj);
			///将新节点加入到Tail
			tail.setNext(node);
			tail=tail.getNext();
			tail.setNext(head);
		}
		size++;
	}

	/**
	 * 出队
	 *
	 * @return
	 */
	public T dequeue() {
		if (head == null) {
			throw new IllegalArgumentException("队列为空！");
		}
		T result = head.getData();
		if (size==0){
			head=null;
			tail=null;
		}else{
			head=head.getNext();
			tail.setNext(head);
		}
		size--;
		return result;
	}


	public static void main(String[] args) {
		CircularLinkedQueue<Object> queue = new CircularLinkedQueue<>();
		queue.queue(1);
		queue.queue(2);
		queue.queue(20);

		System.out.println(queue.dequeue());

		System.out.println(queue.dequeue());

		System.out.println(queue.dequeue());

		queue.queue(10);

		queue.queue(11);

	}
}
